package code;

import java.util.HashMap;
import java.util.Map;


public class BalancedBT {
	static int a=10;
	
	public void call(){
		int a=5;
		System.out.println(this.a);
	}
	public boolean dfs(TreeNode p,Map<TreeNode,Integer> map){
		if(p.left==null && p.right==null){
			map.put(p, 1);
			return true;
		}
		int leftLevel=0;
		if(p.left!=null){
			if(!dfs(p.left,map))
				return false;
			leftLevel=map.get(p.left);
		}
		int rightLevel=0;
		if(p.right!=null){
			if(!dfs(p.right,map))
				return false;
			rightLevel=map.get(p.right);
		}
		if(Math.abs(leftLevel-rightLevel)>1)
			return false;
		int max=leftLevel>rightLevel?leftLevel:rightLevel;
		map.put(p, max+1);
		return true;
	}
    public boolean isBalanced(TreeNode root) {
    	Map<TreeNode,Integer> map=new HashMap<TreeNode,Integer>();
    	if(root==null)
    		return true;
    	if(dfs(root,map))
    		return true;
        return false;
    }
    
    public static void main(String[] args){
    	BalancedBT bbt=new BalancedBT();
    	bbt.call();
//    	TreeNode root=new TreeNode(1);
//    	TreeNode a=new TreeNode(2);
//    	TreeNode b=new TreeNode(3);
//    	TreeNode c=new TreeNode(4);
//    	root.left=a;
//    	a.left=b;
//    	b.left=c;
//    	
//    	int x=-1;
//    	System.out.println(x>>>0);
//    	System.out.println(x>>>32);
    }
}
